package executor;

import java.io.*;
import java.awt.*;
import java.awt.image.*;

/**
Sotto-classe di QuadNode che realizza un quad-tree.
La classe fornisce funzioni per:
<UL>
<LI> Costruire un quadtree da un'immagine;
<LI> Leggere un quadtree da un file quadtree;
<LI> preparare l'immagine troncando il quad-tree con una soglia di errore
  da usare su tutta l'immagine o con un poligono e due soglie da 
  usare rispettivamente fuori e dentro il poligono;
<LI> ottenere l'immagine, l'immagine degli errori e l'immagine della
  suddivisione del quad-tree cosi' troncato;  
<LI> Scrivere su file il quadtree intero o troncato.
<UL>
Il formato del file quadtree e' binario ed e' composto da:
<UL>
<LI>
un intero su 8 bit, che applicato come esponente alla base 2 
fornisce la lunghezza del lato dell'immagine (che e' quadrata).
</UL>
la lista dei nodi del quadtree in ordine di visita in profondita',
dove ciascun nodo e' rappresentato da:
il carattere ; (punto e virgola), se e' un nodo interno, oppure
tre interi su 8 bit che rappresentano le componenti rosso verde blu
del colore del nodo, se e' un nodo foglia.
*/

public class QuadTree extends QuadNode
{

/* ------ ATTRIBUTI ------ */

  public static final int NODE_CHAR = (int)(';');

/* ------ COSTRUTTORI  ------ */

  /** Costruisce quad-tree costituito dal solo nodo radice,
   * nodo di colore nero e larghezza data.
   * @param w   la larghezza del nodo radice da creare
   */
  protected QuadTree(int w)
  {  super(w);  }
    
  /** Costruisce quad-tree costituito dal solo nodo radice,
   * nodo di colore e larghezza dati.
   * @param c   il colore da dare al nodo radice
   * @param w   la larghezza del nodo radice da creare
   */
  protected QuadTree(Color c, int w)
  {  super(c, w);  }

/* ------ METODI PER DECIDERE DOVE TRONCARE IL QUADTREE  ------ */

  /** 
   * Prepara un'immagine nel quadtree marcando come "presi" tutti i nodi 
   * che vi contribuiranno. Usa soglia di tolleranza (255,255,255)
   * percio' prende la radice e l'immagine risultante ha un unico colore.
   * Da chiamare prima di getImage().
   * @see QuadTree#getImage
   */
  public void prepareImage()
  {
    this.prepareSubImage(0, 0, Color.white, null, null, null);
  }

  /** 
   * Prepara un'immagine nel quadtree marcando come "presi" tutti i nodi 
   * che vi contribuiranno.
   * Da chiamare prima di getImage().
   * @param error1   soglia di tolleranza da usare su tutta l'immagine
   * @see QuadTree#getImage
   */
  public void prepareImage(Color error1)
  {
    if (error1==null) error1 = Color.white;
    this.prepareSubImage(0, 0, error1, null, null, null);
  }

  /** 
   * Prepara un'immagine nel quadtree marcando come "presi" tutti i nodi 
   * che vi contribuiranno.
   * @param error1   soglia di tolleranza da usare fuori dal poligono
   * @param pol      il poligono 
   * @param error2   soglia di tolleranza da usare dentro il poligono
   * Da chiamare prima di getImage().
   * @see QuadTree#getImage
   */
  public void prepareImage(Color error1, Polygon pol, Color error2)
  {
    if (pol==null)
    { 
      prepareImage(error1); return; 
    }
    if (error1==null) error1 = Color.white;
    if (error2==null) error2 = Color.white;
    Color error3 = new Color(Math.min(error1.getRed(),error2.getRed()),
                             Math.min(error1.getGreen(),error2.getGreen()),
                             Math.min(error1.getBlue(),error2.getBlue()));
    this.prepareSubImage(0, 0, error1, pol, error2, error3);
  }

/* ------ METODI PER OTTENERE L'IMMAGINE DAL QUADTREE TRONCATO  ------ */

  /** 
   * Costruisce dal quadtree l'immagine definita dai nodi marcati 
   * come "presi". Da chiamare dopo una delle prepareImage(...).
   * @see QuadTree#prepareImage
   */
  public Image getImage()
  {
    PixelMatrix m = new PixelMatrix(width);
    counter = 0;
    this.getSubImage(m, 0, 0);
    return m.thisAsImage();
  }

  /** 
   * Costruisce dal quadtree l'immagine degli errori
   * definita dai nodi marcati 
   * come "presi". Da chiamare dopo una delle prepareImage(...).
   */
  public Image getErrorImage()
  {
    PixelMatrix m = new PixelMatrix(width);
    counter = 0;
    this.getErrorSubImage(m, 0, 0);
    return m.thisAsImage();
  }

  /** 
   * Costruisce dal quadtree l'immagine della suddivisione 
   * definita dai nodi marcati 
   * come "presi". Da chiamare dopo una delle prepareImage(...).
   */
  public Image getSubdivisionImage()
  {
    PixelMatrix m = new PixelMatrix(width);
    counter = 0;
    this.getSubdivisionSubImage(m, 0, 0);
    return m.thisAsImage();
  }

/* ------ METODI PER LEGGERE UN QUADTREE DA FILE ------ */

  /**
  * Legge un quadtree da file.
  * @param in   il file da cui leggere
  * @return     il quad-tree letto
  */
  public static QuadTree read(InputStream in) throws IOException
  {
   /* legge l'esponente che applicato come esponente alla base 2  
   fornisce la lunghezza del lato dell'immagine */
   int exponent = BasicIO.getByte(in);
   int width = 1;
   for (int i=0; i<exponent; i++)
   { width *= 2; } 
   QuadTree root = new QuadTree(width);
   counter = 1;
   if (readTree(in, width, root)) 
   {  root.setError(); return root;  }
   else return null;
  } 

  /**
  * Funzione ricorsiva che legge un nodo e tutto il suo sotto-albero 
  * da file. Chiamata dalla funzione read(InputStream).
  * @param in     il file da cui leggere
  * @param width  larghezza del nodo radice del sotto-albero da leggere
  * @param n      nodo radice del sotto-albero da leggere
  * @return       true se tutto ok, false se errore
  */
  protected static boolean readTree(InputStream in, int width, QuadNode n) throws IOException
  {
    if (width==1) // deve essere foglia
    {
      n.color = BasicIO.readRGB(in);
      return true;
    }
    else
    {
      int cc = BasicIO.getByte(in);
      if (cc==NODE_CHAR) // nodo interno
      {
        n.makeSons();
        counter += 4;
        for (int i=0; i<4; i++)
        {
          if (!readTree(in, width/2, n.son[i])) return false;
        } 
        return true;
      }
      else // foglia
      {
        n.color = BasicIO.readRGB(in,cc);
        return true;
      }
    }
  }

/* ------ METODI PER COSTRUIRE UN QUADTREE DA UN'IMMAGINE ------ */

  /**
  * Costruisce un quadtree a partire da un'immagine.
  * @param im   immagine da cui leggere
  * @param x0   ascissa del punto d'aggancio della parte
  *             di immagine da leggere
  * @param y0   ordinata del punto d'aggancio della parte
  *             di immagine da leggere 
  * @return     il quad-tree letto
  */
  public static QuadTree read(int x0, int y0, int width, Image im)
  {
   PixelMatrix m = new PixelMatrix(x0, y0, width, im);
   QuadTree root = new QuadTree(width);
   counter = 1;
   if (readTree(m, 0, 0, width, root)) 
   {  root.setError(); return root;  }
   else return null;
  } 

  /**
  * Funzione ricorsiva che costruisce un nodo e tutto il suo sotto-albero 
  * a partire da una sotto-parte di immagine. Chiamata dalla funzione
  * read(PixelMatrix).
  * @param m     immagine da cui leggere come matrice di pixel
  * @param x0    ascissa del punto d'aggancio della parte
  *              di immagine da leggere
  * @param y0    ordinata del punto d'aggancio della parte
  *              di immagine da leggere 
  * @param width larghezza della parte di immagine da leggere
  * @param n     nodo radice del sotto-albero da leggere
  */
  protected static boolean readTree(PixelMatrix m, int x0, int y0, int width, QuadNode n)
  {
    if (width==1) // deve essere foglia
    {
      n.color = m.getColor(x0, y0);
      return true;
    }
    else // nodo interno
    {
      boolean divide = false;
      // guarda se i pixel sono tutti uguali o quasi
      {
        int c = m.getColor(x0, y0);
        int i, j;
        for (i=0; i<width & !divide; i++)
        for (j=0; j<width & !divide; j++)
        {
          int c1 = m.getColor(x0+i, y0+j);
          if (Math.abs(QuadColor.getRed(c)-QuadColor.getRed(c1))>0)
             divide = true;
          else if (Math.abs(QuadColor.getGreen(c)-QuadColor.getGreen(c1))>0)
             divide = true;
          else if (Math.abs(QuadColor.getBlue(c)-QuadColor.getBlue(c1))>0)
             divide = true;
        }
      }
      
      if (!divide) // se non lo devo dividere
      {
        n.color = m.getColor(x0, y0);
        return true;  
      }      
      else // se lo devo dividere 
      {
        n.makeSons();
        counter += 4;
        if (!readTree(m, n.anchorX(x0, NW), 
                 n.anchorY(y0, NW), width/2,
                 n.son[n.sonIndex(NW)])) return false;
        if (!readTree(m, n.anchorX(x0, NE), 
                 n.anchorY(y0, NE), width/2,
                 n.son[n.sonIndex(NE)])) return false;
        if (!readTree(m, n.anchorX(x0, SW), 
                 n.anchorY(y0, SW), width/2,
                 n.son[n.sonIndex(SW)])) return false;
        if (!readTree(m, n.anchorX(x0, SE), 
                 n.anchorY(y0, SE), width/2,
                 n.son[n.sonIndex(SE)])) return false;
      }
      return true;
    }
  }

/* ------ METODI PER SCRIVERE UN QUADTREE SU FILE ------ */

  /**
  * Scrive un quadtree su file.
  * @param out     file su cui scrivere
  * @param root    quad-tree da scrivere
  */
  public static boolean write(OutputStream out, QuadTree root) throws IOException
  {
   /* scrive l'esponente che applicato come esponente alla base 2  
   fornisce la lunghezza del lato dell'immagine */
   int exponent = 0;
   int width = root.getWidth();
   while (width>1)
   { 
     exponent++;
     width /= 2;
   } 
   BasicIO.putByte(out, exponent);
   counter = 1;
   if (writeTree(out, root.getWidth(), root)) return true;
   else return false;
  } 

  /**
  * Funzione ricorsiva che scrive un nodo e tutto il suo sotto-albero 
  * su file. Chiamata dalla funzione write(OutputStream, QuadNode).
  * @param out     file su cui scrivere
  * @param width   larghezza della radice del sotto-albero da scrivere
  * @param n       nodo radice del sotto-albero da scrivere
  */
  protected static boolean writeTree(OutputStream out, int width, QuadNode n) throws IOException
  {
    if (n.isLeaf()) // foglia
    {
      /* Attenzione: se la componente rossa valesse esattamente NODE_CHAR
         rileggendo verrebbe interpretato come nodo interno. 
         Allora se e' cosi' aggiungo 1 al rosso, non si vedra' molto... */
      if (QuadColor.getRed(n.color)==NODE_CHAR)
        n.color = QuadColor.makeColor(QuadColor.getRed(n.color)+1,
                                      QuadColor.getGreen(n.color),
                                      QuadColor.getBlue(n.color));
      BasicIO.writeRGB(out, n.color);
      return true;
    }
    else // nodo interno
    {
      BasicIO.putByte(out, NODE_CHAR);
      counter += 4;
      for (int i=0; i<4; i++)
      {
          if (!writeTree(out, width/2, n.son[i])) return false;
      } 
      return true;
    }
  }

  /**
  * Scrive un quadtree su file troncandolo ai nodi presi.
  * @param out     file su cui scrivere
  * @param root    quad-tree da scrivere
  */
  public static boolean writeTaken(OutputStream out, QuadTree root) throws IOException
  {
   /* scrive l'esponente che applicato come esponente alla base 2  
   fornisce la lunghezza del lato dell'immagine */
   int exponent = 0;
   int width = root.getWidth();
   while (width>1)
   { 
     exponent++;
     width /= 2;
   } 
   BasicIO.putByte(out, exponent);
   counter = 1;
   if (writeTreeTaken(out, width, root)) return true;
   else return false;
  } 

  /**
  * Funzione ricorsiva che scrive un nodo e tutto il suo sotto-albero 
  * su file, troncando ai nodi presi.
  * Chiamata dalla funzione writeTaken(OutputStream, QuadNode).
  * @param out     file su cui scrivere
  * @param width   larghezza della radice del sotto-albero da scrivere
  * @param n       nodo radice del sotto-albero da scrivere
  */
  protected static boolean writeTreeTaken(OutputStream out, int width, QuadNode n) throws IOException
  {
    if (n.taken) // foglia o nodo interno accettato
    {
      /* Attenzione: se la componente rossa valesse esattamente NODE_CHAR
         rileggendo verrebbe interpretato come nodo interno. 
         Allora se e' cosi' aggiungo 1 al rosso, non si vedra' molto... */
      if (QuadColor.getRed(n.color)==NODE_CHAR)
        n.color = QuadColor.makeColor(QuadColor.getRed(n.color)+1,
                                      QuadColor.getGreen(n.color),
                                      QuadColor.getBlue(n.color));
      BasicIO.writeRGB(out, n.color);
      return true;
    }
    else // nodo interno non accettato
    {
      BasicIO.putByte(out, NODE_CHAR);
      counter += 4;
      for (int i=0; i<4; i++)
      {
          if (!writeTreeTaken(out, width/2, n.son[i])) return false;
      } 
      return true;
    }
  }

/* ------ METODI PER LEGGERE STATISTICHE ------ */

  /** Ritorna il contatore delle statistiche, che vale:
   * <UL>
   * <LI>Se chiamato subito dopo getImage, il numero 
   * di nodi che contribuiscono all'immagine;
   * <LI>Stessa cosa se chiamato subito dopo getErrorImage o
   * getSubdivisionImage;
   * <LI>Se chiamato subito dopo read (in entrambe le forme
   * da file o da un'immagine), il numero di nodi letti;
   * <LI>Se chiamato subito dopo write o writeTaken, il
   * numero di nodi scritti.   
   * </UL>
   * @return   valore come spiegato sopra
   */
  public int getCounter() {  return counter;  }

}
